package ru.susu.algebra.algorithms;

import java.math.BigInteger;

import ru.susu.algebra.pair.Pair;

/**
 * Расширенный алгоритм Евклида, решает уравнение ax+by=c в целых числах.
 * Алгоритм работает рекурсивно:
 * a1*x + b1*y = c1
 * b1*x + a1%b1*y = c1 и тд.
 *
 * При этом полученное решение используется в расчете решения текущего уравнения по формулам:
 * x = ty
 * y=tx-a/b*ty
 *
 * @author akargapolov
 * @since: 21.06.2010
 */
public class ExtendedEuclidAlgorithm
{
	/**
	 * Решает уравнение ax+by=c алгоритмом Евклида.
	 * @return пару - решение уравнения {@link Pair}, где ключом является x, а значением y, либо null, если решения нет
	 */
	public Pair<BigInteger, BigInteger> solve(BigInteger a, BigInteger b, BigInteger c)
	{
		if (b.equals(BigInteger.ZERO))
		{
			if (a.equals(BigInteger.ZERO))
			{
				if (c.equals(BigInteger.ZERO))
				{
					return new Pair<BigInteger, BigInteger>(BigInteger.ZERO, BigInteger.ZERO);
				}
				else
				{
					return null;
				}
			}
			if (!c.mod(a).equals(BigInteger.ZERO))
			{
				return null;
			}
			//x = c / a, y = 0
			return new Pair<BigInteger, BigInteger>(c.divide(a), BigInteger.ZERO);
		}

		Pair<BigInteger, BigInteger> recSolution = solve(b, a.mod(b), c);
		if (recSolution == null)
			return null;
		BigInteger x = recSolution.getValue(); //x = ty
		BigInteger y = recSolution.getKey().subtract(a.divide(b).multiply(recSolution.getValue())); //y=tx-a/b*ty
		return new Pair<BigInteger, BigInteger>(x, y);
	}
}
